import queue
import random
c_ij = [
    [0,5,21,13,6,15,12,20],
    [5,0,16,18,7,12,19,17],
    [21,16,0,33,16,7,17,11],
    [13,18,33,0,17,26,16,29],
    [6,7,16,17,0,9,12,14],
    [15,12,7,26,9,0,10,5],
    [18,19,17,16,12,10,0,13],
    [20,17,11,29,14,5,13,0]
]
N = len(c_ij)
inf = 100000

def Kruskal(c_ij):
    #edges存储[权值，端点，端点]，按权值从小到大排序
    edges = []
    for i in range(N):
        for j in range(N):
            if j != i:
                edges.append((c_ij[i][j],i,j))
    edges.sort()

    mst = []#mst记录生成树的结点
    reps = [i for i in range(N)]#reps存储每个结点当前所属元组的标识，初始时每个结点标识都不同
    for w,v1,v2 in edges:
        
        if reps[v1] != reps[v2]:
            mst.append((v1,v2,w))
            if len(mst) == N - 1:
                break

            #讲v1,v2的标识统一
            reps1,reps2 = reps[v1],reps[v2]
            for i in range(N):
                if reps[i] == reps1:
                    reps[i] = reps2
    return mst

def Prim(c_ij):
    mst = [None] * N
    cands = queue.PriorityQueue()
    cands.put((0,0,0))
    count = 0
    while count < N and cands:
        w,v1,v2 = cands.get()
        if mst[v2]:
            continue
        mst[v2] = (v1,v2,w)
        count += 1
        for v in range(N):
            if not mst[v]:
                cands.put((c_ij[v2][v],v2,v)) 
    return mst

def perfect_match(mst):
    #找出mst中度数为奇数的结点
    # print(mst)
    mst_ = [(item[0],item[1]) for item in mst]
    count = [0] * N
    for v1,v2 in mst_:
        if v1 != v2:
            count[v1] += 1
            count[v2] += 1
    # print(count)
    odd_nodes = []
    for i in range(N):
        if count[i]%2:
            odd_nodes.append(i)
    # print(odd_nodes)
    '''贪心求一个匹配（解决例题没问题），学会完美匹配算法再回来补'''
    while odd_nodes:
        vi = odd_nodes[0]
        tem = inf
        vj = None
        for j in odd_nodes:
            if j != vi and c_ij[vi][j] <= tem:
                tem = c_ij[vi][j]
                vj = j
        mst_.append((vi,vj)) if (vj,vi) in mst_ else mst_.append((vj,vi))
        odd_nodes.remove(vi)
        odd_nodes.remove(vj)
    print(mst_)
    return mst_


def eul(mst_):
    mst1 = list(mst_)
    mst1.remove((0,0))
    # pioneer = random.choice(mst1) #起点随机时结果不一定最优
    # route = [pioneer[0]]
    route = [3] 
    def get_sub(start):
        sub_route = [start]
        curr_node = start
        i = 0
        while i < len(mst1):
            if mst1[i][0] == curr_node :
                curr_node = mst1[i][1]
                sub_route.append(mst1[i][1])
                mst1.remove(mst1[i])
                i = 0
            elif mst1[i][1] == curr_node :
                curr_node = mst1[i][0]
                sub_route.append(mst1[i][0])
                mst1.remove(mst1[i])
                i = 0
            else:
                i += 1    
        return sub_route


    while mst1:
        insert_node = None
        for i in range(len(route)):
            for v1,v2 in mst1:
                if v1 == route[i]:
                    start = v1
                    insert_node = i
                    break
                elif v2 == route[i]:
                    start = v2
                    insert_node = i
                    break
        print("mst1:",mst1)
        sub_route = get_sub(start)
        print("sub:",sub_route)
        route = route[:insert_node] + sub_route + route[insert_node+1:]
        print(route)
              
    return route

def get_tsp(route_eul,c_ij):
    route = []
    for item in route_eul:
        if item not in route:
            route.append(item)
    leng = 0
    for i in range(len(route)):
        leng += c_ij[route[i-1]][route[i]]
    return route,leng

mst = Prim(c_ij)
mst_ = perfect_match(mst)
eul_route = eul(mst_)
print(eul_route)
print(get_tsp(eul_route,c_ij))

